package org.example.myleet.p1190;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * 1 ms
 * 执行用时： 1 ms , 在所有 Java 提交中击败了 98.96% 的用户
 * 内存消耗： 36 MB , 在所有 Java 提交中击败了 99.93% 的用户
 *
 * 直接模拟，用栈记录最近一个"("左括号的位置，遇到右括号时做一次翻转
 */
public class Solution {
    public String reverseParentheses(String s) {
        Deque<Integer> stack = new LinkedList<>();
        int i = 0, ti = 0, len = s.length();
        char[] target = new char[len];
        while (i < len) {
            char c = s.charAt(i);
            if (c == '(') {
                stack.push(ti);
            } else if (c == ')') {
                Integer start = stack.pop();
                reverseRange(target, start, ti);
            } else {
                target[ti++] = c;
            }
            ++i;
        }
        return new String(Arrays.copyOf(target, ti));
    }

    /**
     * 逆转部分区域的字符顺序，包括start，不包括end
     */
    private void reverseRange(char[] target, int start, int end) {
        int s = start, e = end - 1;
        char c;
        while (s < e) {
            c = target[s];
            target[s] = target[e];
            target[e] = c;
            ++s;
            --e;
        }
    }
}
